package com.sheng.leetcode.year2023.month04.day18;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/04/18
 * <p>
 * 1026. 节点与其祖先之间的最大差值<p>
 * <p>
 * 给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。<p>
 * （如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）<p>
 * <p>
 * 示例 1：<p>
 * 输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]<p>
 * 输出：7<p>
 * 解释：<p>
 * 我们有大量的节点与其祖先的差值，其中一些如下：<p>
 * |8 - 3| = 5<p>
 * |3 - 7| = 4<p>
 * |8 - 1| = 7<p>
 * |10 - 13| = 3<p>
 * 在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。<p>
 * <p>
 * 示例 2：<p>
 * 输入：root = [1,null,2,null,0,3]<p>
 * 输出：3<p>
 * <p>
 * 提示：<p>
 * 树中的节点数在 2 到 5000 之间。<p>
 * 0 <= Node.val <= 10^5<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor">1026. 节点与其祖先之间的最大差值</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1026 {

    @Test
    public void test01() {
        TreeNode node = new TreeNode(6);
        node.left = new TreeNode(4);
        node.right = new TreeNode(7);
        TreeNode node1 = new TreeNode(3);
        node1.left = new TreeNode(1);
        node1.right = node;
        TreeNode node2 = new TreeNode(10);
        TreeNode node3 = new TreeNode(14);
        node3.left = new TreeNode(13);
        node2.right = node3;
        TreeNode root = new TreeNode(8);
        root.left = node1;
        root.right = node2;
        System.out.println(new Solution().maxAncestorDiff(root));
    }
}

class Solution {

    int max = 0;

    public int maxAncestorDiff(TreeNode root) {
        calculate(root, root.val, root.val);
        return max;
    }

    public void calculate(TreeNode root, Integer ma, Integer mi) {
        // 求出结点 root 对应的子节点中的最大值和最小值，然后分别对当前结点 root 的 val 进行计算，
        // 取最大的一个，然后赋值给 max，然后遍历子节点，最后获取的就是最大差值
        // 优化
        if (root == null) {
            return;
        }
        max = Math.max(max, Math.max(Math.abs(root.val - ma), Math.abs(root.val - mi)));
        ma = Math.max(ma, root.val);
        mi = Math.min(mi, root.val);
        calculate(root.left, ma, mi);
        calculate(root.right, ma, mi);
        // 226 ms
//        if (root == null) {
//            return;
//        }
//        max(root.left, root.val, root.val, root.val);
//        calculate(root.left);
//        max(root.right, root.val, root.val, root.val);
//        calculate(root.right);
    }

    public void max(TreeNode root, Integer num, Integer ma, Integer mi) {
        if (root == null) {
            max = Math.max(max, Math.max(Math.abs(num - ma), Math.abs(num - mi)));
            return;
        }
        ma = Math.max(ma, root.val);
        mi = Math.min(mi, root.val);
        max(root.left, num, ma, mi);
        max(root.right, num, ma, mi);
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
